/*
 * acm1366.c
 *
 *  Created on: 11 Apr 2010
 *      Author: xuxu
 */

#include<stdio.h>
#include<string.h>
int cash[11][2];
int n;
int count;
int bo;
int mark[100001];
int main()
{
	int i,j,k;
	int max;
	int t;
	while(scanf("%d%d",&count,&n)!=EOF)
	{
		for(i=0;i<n;i++)
			scanf("%d%d",&cash[i][0],&cash[i][1]);
		memset(mark,0,sizeof(mark));
		mark[0]=1;
		max=0;
		for(i=0;i<n;i++)
		{
			for(j=max;j>=0;j--)
			{
				if(mark[j])
				{
					for(k=1;k<=cash[i][0];k++)
					{
						t=k*cash[i][1]+j;
						if(t>count)
							break;
						max=max>t?max:t;
						mark[t]=1;
					}
				}
			}
		}
		printf("%d\n",max);
	}
	return 0;
}
